package com.review.bfs;

import java.util.*;

public class TraversalGraphBFS {
    // https://www.bilibili.com/video/BV1Ks411575U

    private void initGraph(HashMap<Character, List<Character>> graph) {
        graph.put('A', Arrays.asList('B', 'C'));
        graph.put('B', Arrays.asList('A', 'C', 'D'));
        graph.put('C', Arrays.asList('A', 'B', 'D', 'E'));
        graph.put('D', Arrays.asList('B', 'C', 'E', 'F'));
        graph.put('E', Arrays.asList('C', 'D'));
        graph.put('F', Collections.singletonList('D'));
    }
    private List<Character> bfs(HashMap<Character, List<Character>> graph, char start) {
        // 构建图
        initGraph(graph);
        // 结果集
        ArrayList<Character> res = new ArrayList<>();
        // 判断节点是否被访问过了
        Set<Character> seen = new HashSet<>();
        // 队列
        Queue<Character> queue = new LinkedList<>();
        queue.add(start);
        while (queue.size() != 0) {
            Character poll = queue.poll();
            if (!res.contains(poll)) {
                res.add(poll);
            }
            seen.add(poll);
            for (Character tmp : graph.get(poll)) {
                if (!seen.contains(tmp)) {
                    queue.add(tmp);
                }
            }
        }
        return res;
    }

    // dfs就是将队列直接换位栈
    private List<Character> dfs(HashMap<Character, List<Character>> graph, char start) {
        // 构建图
        initGraph(graph);
        // 结果集
        ArrayList<Character> res = new ArrayList<>();
        // 判断节点是否被访问过了
        Set<Character> seen = new HashSet<>();
        // 栈
        Stack<Character> stack = new Stack<>();
        stack.add(start);
        while (stack.size() != 0) {
            Character poll = stack.pop();
            if (!res.contains(poll)) {
                res.add(poll);
            }
            seen.add(poll);
            for (Character tmp : graph.get(poll)) {
                if (!seen.contains(tmp)) {
                    stack.add(tmp);
                }
            }
        }
        return res;
    }

    // 记录结构
    private HashMap<Character, Character> remember(HashMap<Character, List<Character>> graph, char start) {
        // 构建图
        initGraph(graph);
        // 结果集
        ArrayList<Character> res = new ArrayList<>();
        // 判断节点是否被访问过了
        Set<Character> seen = new HashSet<>();
        // 队列
        Queue<Character> queue = new LinkedList<>();
        queue.add(start);
        // 记录当前节点的前一个节点
        HashMap<Character, Character> record = new HashMap<>();
        record.put(start, null);
        while (queue.size() != 0) {
            Character poll = queue.poll();
            if (!res.contains(poll)) {
                res.add(poll);
            }
            seen.add(poll);
            for (Character tmp : graph.get(poll)) {
                if (!seen.contains(tmp)) {
                    queue.add(tmp);
                    record.put(tmp, poll);
                }
            }
        }
        return record;
    }

    public static void main(String[] args) {
        HashMap<Character, List<Character>> graph = new HashMap<>();
        TraversalGraphBFS traversalGraphBFS = new TraversalGraphBFS();
        // BFS
        List<Character> bfs = traversalGraphBFS.bfs(graph, 'E');
        for (Character bf : bfs) {
            System.out.print(bf);
        }
        System.out.println();
        // DFS
        List<Character> dfs = traversalGraphBFS.dfs(graph, 'A');
        for (Character df : dfs) {
            System.out.print(df);
        }
        System.out.println();
        // record 记录当前节点的父节点
        HashMap<Character, Character> record = traversalGraphBFS.remember(graph, 'A');
        for (Character character : record.keySet()) {
            System.out.println(character+":"+record.get(character));
        }
    }
}
